剑指 Offer 33. 二叉搜索树的后序遍历序列

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。

参考以下这颗二叉搜索树：

     5
    / \
   2   6
  / \
 1   3

示例 1：

输入: [1,6,3,2,5]
输出: false

示例 2：

输入: [1,3,2,6,5]
输出: true

递归分治

• 逻辑

  • 从后向前遍历，寻找第一个小于根节点的元素下标 i（这样可以保证右子树均大于根节点）

  • 对左子树正确性进行判断，即从 i 向前进行遍历，若发现大于根节点的值，则判断不是搜索二叉树，返回 false

  • 对左右子树递归

func verifyPostorder(postorder []int) bool {
	if len(postorder) == 0 {
		return true
	}
	rootVal := postorder[len(postorder)-1]
	var i int
	for i = len(postorder) - 1; i >= 0; i-- {
		// 找到第一个小于rootVal的下标
		if postorder[i] < rootVal {
			break
		}
	}

	for j := i; j >= 0; j-- {
		if postorder[j] > rootVal {
			return false
		}
	}

	return verifyPostorder(postorder[:i+1]) && verifyPostorder(postorder[i+1:len(postorder)-1])
}